1. Field of the Invention
This invention relates to data processing systems and more specifically to a data processing system which provides for execution of nested subroutines and interrupts.
2. Description of the Prior Art
The operations carried out in a data processing system and the order in which they occur are stated by means of a program stored in a memory. To alleviate the programmer's problem of completely specifying each series of operations to be performed and to better utilize the capabilities of a data processor, common functions which may be required several times in one program or may be utilized in other programs are usually provided. Each common function may be specified as a subroutine wherein a subroutine includes a sequence of instructions.
Subroutines may be utilized for a number of common functions, for example, trigonometric functions using mathematical approximations. Rather than rewrite the series of operations several times, the programmer merely has to write one set of instructions to perform the operation and call it a number of times. Thus, for a routine requiring a value of a trigonometric function, such as cosine, a branch operation to the cosine subroutine in the digital data processor is executed.
Often times it has been found that one subroutine will call another subroutine in order to complete its operation. When this situation occurs, complications arise since the return address, i.e., the next address from the branching subroutine must be stored and recalled by the data processor. Thus while the efficiency of the overall program is enhanced by providing for a particular function in only one place in the data processor, it is often times found that inefficiencies arise in calling and returning from the various subroutines both as to time considerations and hardware and/or space limitations.
In the prior art, a number of solutions for transferring to and from subroutines have bee provided. One solution involves the transferral of the next instruction location to the first location of the subroutine. In this design, the last subroutine instruction accesses the first location of the subroutine. This first location contains the return address to the next instruction (i.e., one instruction past the instruction that branched to the subroutine) thus enabling the data processor to continue sequencing through the program. This method suffers disadvantages since handling of several common transfers complicates the situation. For example, it is often advantageous to transfer operations from a first subroutine to a second subroutine which utilizes the first subroutine. In other situations, it may be advantageous if the first subroutine recalls itself. These transfers are difficult, and sometimes impossible to achieve with data processing systems of the above types without modification or without increasing the number of instructions. When the first subroutine is called for a first time, the the address of next microinstruction in the main routine is transferred to the first subroutine location. When the first subroutine is recalled by an intermediate routine, the address of the next instruction in the intermediate routine is transferred to the same location in the first subroutine thus destroying the original contents. As a result, while the first subroutine can return to the intermediate routine, it cannot return to the main routine.
In data processing systems which permit a first or second subroutine to recall the first subroutine, an instruction may be provided to move the return address to a specified storage location. The last subroutine instruction is then altered so as to include the address of the specified storage location. Although this system permits one subroutine to call another subroutine, i.e., to have the latter subroutine nest, and permit a partially completed subroutine to be subsequently used for other purposes, one reserve memory location and several instructions are required for each nesting level. Increasing the number of these memory locations for each nested subroutine increases the complexity of the control circuitry. In addition, programming complexity is increased because the last subroutine instruction must be modified to address the proper memory location for each subroutine. Therefore, this approach becomes more cumbersome as the number of nesting levels are increased.
Another type of data processing system utilizes vacant locations in memory for storing the return addresses of the subroutine or routine previously executed. The last instruction of the subroutine branches to a designated memory location. In order to exploit this system, however, two registers, one a pointer to the vacant memory locations and another which provides for the current value of the register and the memory address, are required. While this type of data processing unit overcomes some of the previous problems, it still results in supplemental instructions to indicate each new level of subroutines with a concurrent greater execution time required.
A more recent solution to this problem is found in U.S. Pat. No. 3,909,797 entitled, "Data Processing System Utilizing Control Store Unit and Push Down Stack for Nested Subroutines", which is incorporated herein by reference. In this patent, the data processing system has a microprogrammed control store unit which enables the sequencing of the central processing subsystem. This patent provides for the nesting of subroutines programmed within the firmware that controls the control store unit, but the principles of the invention are equally applicable to software programs or firmware microprograms. The control store unit provides a branching microinstruction to a microprogram subroutine via a microcommand for enabling the return address of the current operating microprogram routine to be stored. The microcommand also enables a push down stack such that previously stored return microprogram addresses are moved down (pushed) one level. Upon completion of the microprogram subroutine, the control store unit provides a branch field for enabling a multiplexer to select the return address contained on the top of the push down stack and provide it to the current address register in the system. The branch field also raises one level the previously stored return addresses in the push down stack.
Interrupts are used in a data processing system to make it responsive to events that occur asynchronously to the execution of the program. These asynchronous events may be faults within the data processing system or change of status of devices controlled by the data processing system. For example, by interrupting the data processing system, an input/output (I/O) device can signal that it requires attention or service by the data processing system. Such interrupts can be used to signal the completion of an I/O operation or a system fault such as a memory error. As in the case of subroutines, interrupts can divert the program flow. In the case of interrupts, program flow is diverted to an interrupt service routine which is programmed to handle the type of event that caused the interrupt. Upon completion of the execution of the interrupt service routine, the interrupt service routine must cause the data processor to resume execution of the program at the return address that was stored upon interruption.
One method for storing the return address is to assign fixed locations within memory to each type of interrupt for storing the return address of the program that was interrupted. Using this method, when the interrupt service routine is completed, it can reload the data processor's program counter from the fixed memory location associated with a particular type of interrupt and resume execution of the program that was executing just prior to the occurrence of the interrupt. This method has the disadvantage that interrupt service routines can not easily share common program instructions because in order to return to the interrupted program, the service routine must retrieve the interrupt return address from a fixed memory location that differs with each interrupt.
A different approach to handling interrupt return addresses is found in U.S. Pat. No. 4,340,933 entitled "Data Processing System Having Centralized Nonexistent Memory Address Detection", which is incorporated herein be reference. In this patent, which deals with hardware interrupts that interrupt the execution of a firmware microprogram, the microprogram return address is stored in a special register (the hardware interrupt return address register) and further hardware interrupts are prevented until completion of the microprogram hardware interrupt service routine. Inhibiting subequent interrupts insures that the first microprogram return address stored in the hardware interrupt return address register will not be destroyed by a second return address being stored over it by the occurrence of a second hardware interrupt. This method, although allowing interrupt service routines to share common program instructions because all interrupt service routines restore execution to the interrupted program by reloading the program counter from the one interrupt return address register, still has the disadvantage that interrupts and subroutines can not easily share common program instructions.
Therefore, what is needed is a method of storing return addresses that will allow the nesting of subroutine calls and the servicing of interrupts in a common and efficient manner.